#include <string>
#include <vector>
#include <unordered_map>

using namespace std;

// 用类描述实现前缀树。不推荐！
// 测试链接 : https://leetcode.cn/problems/implement-trie-ii-prefix-tree/
// 相似的题目：208. 实现 Trie (前缀树)：https://leetcode.cn/problems/implement-trie-prefix-tree/

// 路是数组实现的
// 提交时把类名、构造方法、析构方法改为 Trie
class Trie1
{
private:
    class TrieNode
    {
    public:
        int pass;
        int end;
        vector<TrieNode*> nexts;

        TrieNode()
        {
            pass = 0;
            end = 0;
            nexts.resize(26, nullptr);
        }
    };

    TrieNode* root = nullptr; // 哨兵位头结点

    // 这个函数可以不写
    void destroy(TrieNode* node)
    {
        // 先销毁孩子节点，才能够销毁自己
        for(int i = 0; i < 26; ++i)
        {
            if(node->nexts[i] != nullptr)
            {
                // node->nexts[i]不为空,则说明有节点,需要递归释放节点
                destroy(node->nexts[i]);
            }
        }
        delete node;
    }

public:
    // 析构函数其实也可以不写
    ~Trie1()
    {
        destroy(root);
    }

    Trie1() 
    {
        root = new TrieNode();
    }
    
    void insert(string word) 
    {
        TrieNode* node = root;
        ++node->pass;
        for(int i = 0, path; i < word.size(); ++i) // 从左往右遍历字符
        {
            path = word[i] - 'a'; // 由字符对应成走向哪条路
            if(node->nexts[path] == nullptr)
            {
                node->nexts[path] = new TrieNode();
            }
            node = node->nexts[path];
            ++node->pass;
        }
        ++node->end;    
    }
    
    // 查询前缀树里，word 单词出现了几次
    int countWordsEqualTo(string word) 
    {
        TrieNode* node = root;
        for(int i = 0, path; i < word.size(); ++i)
        {
            path = word[i] - 'a';
            if(node->nexts[path] == nullptr) return 0;
            node = node->nexts[path];
        }
        return node->end;
    }
    
    // 查询前缀树里，有多少单词以 prefix 做前缀
    int countWordsStartingWith(string prefix) 
    {
        TrieNode* node = root;
        for(int i = 0, path; i < prefix.size(); ++i)
        {
            path = prefix[i] - 'a';
            if(node->nexts[path] == nullptr) return 0;
            node = node->nexts[path];
        }
        return node->pass;
    }

    // 如果之前 word 插入过前缀树，那么此时删掉一次
    // 如果之前 word 没有插入过前缀树，那么什么也不做
    void erase(string word) 
    {
        if(countWordsEqualTo(word) > 0)
        {
            TrieNode* node = root;
            --node->pass;
            for(int i = 0, path; i < word.size(); ++i)
            {
                path = word[i] - 'a';
                if(--node->nexts[path]->pass == 0)
                {
                    destroy(node->nexts[path]); // 这里其实可以不写，因为 OJ 平台一般不会检查内存泄漏
                    node->nexts[path] = nullptr;
                    return;
                }
                node = node->nexts[path];
            }
            --node->end;
        }
    }
};

// 路是哈希表实现的
// 提交时把类名、构造方法、析构方法改为 Trie
class Trie2
{
private:
    class TrieNode
    {
    public:
        int pass;
        int end;
        unordered_map<char, TrieNode*> nexts;

        TrieNode()
        {
            pass = 0;
            end = 0;
        }
    };


    TrieNode* root = nullptr; // 哨兵位头结点

    // 这个函数可以不写
    void destroy(TrieNode* node)
    {
        // 先销毁孩子节点，才能够销毁自己
        for(auto kv : node->nexts)
        {
            char path = kv.first;
            destroy(kv.second);
        }
        delete node;
    }

public:
    // 析构函数其实也可以不写
    ~Trie2()
    {
        destroy(root);
    }

    Trie2() 
    {
        root = new TrieNode();
    }
    
    void insert(string word) 
    {
        TrieNode* node = root;
        ++node->pass;
        for(int i = 0, path; i < word.size(); ++i) // 从左往右遍历字符
        {
            path = word[i]; // 由字符对应成走向哪条路
            if(!node->nexts.count(path))
            {
                node->nexts[path] = new TrieNode();
            }
            node = node->nexts[path];
            ++node->pass;
        }
        ++node->end;    
    }
    
    // 查询前缀树里，word 单词出现了几次
    int countWordsEqualTo(string word) 
    {
        TrieNode* node = root;
        for(int i = 0, path; i < word.size(); ++i)
        {
            path = word[i];
            if(!node->nexts.count(path)) return 0;
            node = node->nexts[path];
        }
        return node->end;
    }
    
    // 查询前缀树里，有多少单词以 prefix 做前缀
    int countWordsStartingWith(string prefix) 
    {
        TrieNode* node = root;
        for(int i = 0, path; i < prefix.size(); ++i)
        {
            path = prefix[i];
            if(!node->nexts.count(path)) return 0;
            node = node->nexts[path];
        }
        return node->pass;
    }

    // 如果之前 word 插入过前缀树，那么此时删掉一次
    // 如果之前 word 没有插入过前缀树，那么什么也不做
    void erase(string word) 
    {
        if(countWordsEqualTo(word) > 0)
        {
            TrieNode* node = root;
            TrieNode* next;
            --node->pass;
            for(int i = 0, path; i < word.size(); ++i)
            {
                path = word[i];
                next = node->nexts[path];
                if(--next->pass == 0)
                {
                    destroy(next); // 这里其实可以不写，因为 OJ 平台一般不会检查内存泄漏
                    node->nexts.erase(path);
                    return;
                }
                node = next;
            }
            --node->end;
        }
    }
};